package Solution.problem078.Subsets;

import java.util.ArrayList;
import java.util.List;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/06/13 14:17
 */
public class Solution {
    static List<List<Integer>> res;
    public static List<List<Integer>> subsets(int[] nums) {
        res=new ArrayList<>();
        if(nums==null||nums.length==0){
            return res;
        }

        for(int i=0;i<=nums.length;i++){
            combine(nums,nums.length,i);
        }
        return res;
    }


    private static List<List<Integer>> combine(int[] nums,int n, int k) {

        List<Integer> tmp = new ArrayList<>();
        dfs(nums,tmp, n, k, 1);
        return res;
    }

    private static void dfs(int[] nums,List<Integer> tmp, int n, int k, int m) {
        /*是否放够了k个数*/
        if (k == 0) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = m; i <= n; i++) {
            tmp.add(nums[i-1]);
            dfs(nums,tmp, n, k - 1, i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }

    public static void main(String[] args){
        int[] nums=new int[]{1,2,3,4};
        System.out.println(subsets(nums));
    }
}
